Operating System
OS - Processes
- What is a process? How is it different from a program?
Answer: Program: A passive entity, simply a file containing a set of instructions (code) stored on disk. Process: An active entity. It is a program in execution. It includes the program counter, stack, data section, and heap.
Difference: A program is static (just code), while a process is dynamic (code + execution context). Multiple processes can run the same program (e.g., opening two Chrome windows). - What are the different states of a process?
Answer: The typical process states are:
- New:The process is being created.
- Ready: The process is loaded into memory and is waiting to be assigned to the CPU.
- Running: Instructions are being executed on the CPU.
- Waiting/Blocked: The process is waiting for some event to occur (e.g., I/O completion).
- Terminated: The process has finished execution.
- What is a Process Control Block (PCB)? What information does it contain?
Answer: The PCB is a data structure maintained by the operating system for every process. It contains all the information needed to manage the process. It includes:
- Process State: (Running, Ready, etc.)
- Process ID (PID): Unique identifier.
- Program Counter: Address of the next instruction to execute.
- CPU Registers: Accumulator, index registers, stack pointers.
- CPU Scheduling Info: Priority, pointers to scheduling queues.
- Memory-Management Info: Base and limit registers, page tables.
- I/O Status Info: List of open files, devices allocated.
- Define Context Switching.
Answer: Context switching is the mechanism where the CPU switches from one process to another. The OS saves the current state (PCB) of the old process and loads the saved state (PCB) of the new process. While it allows multitasking, it is considered overhead because the CPU spends time switching rather than executing user processes.
- Consider processes with the following burst times (in ms): P1: 24, P2: 3, P3: 3. Assume all arrive at time 0. Calculate the average waiting time for FCFS (First-Come, First-Served) and SJF (Shortest Job First).
Answer:
- FCFS (Order: P1, P2, P3): - Waiting Time: P1=0, P2=24, P3=27. - Average = (0 + 24 + 27) / 3 = 17 ms. - SJF (Non-preemptive, Order: P2, P3, P1): - Waiting Time: P2=0, P3=3, P1=6. - Average = (0 + 3 + 6) / 3 = 3 ms. - Conclusion: SJF significantly reduces average waiting time. - Explain Round Robin scheduling with an example.
Answer: Round Robin is preemptive. Each process gets a small unit of CPU time called a Time Quantum (e.g., 4ms). If the process finishes within that time, it releases the CPU. If not, it is preempted and moved to the back of the ready queue.
Example: Processes P1 (Burst: 5), P2 (Burst: 3), Quantum = 2. - Time 0-2: P1 runs. P1 remaining = 3. - Time 2-4: P2 runs. P2 finishes (Burst 3). - Time 4-6: P1 runs. P1 remaining = 1. - Time 6-7: P1 runs and finishes. - Pros: Fair, responsive. Cons: Poor if quantum is too large (becomes FCFS) or too small (too many context switches). - What is the difference between Preemptive and Non-preemptive scheduling?
Answer:
- Preemptive: The OS can forcibly remove a process from the CPU (e.g., when a higher-priority process arrives or a time quantum expires). Allows better responsiveness. (e.g., Round Robin, SRTF).
- Non-preemptive: A process holds the CPU until it either terminates or requests I/O. Once a process gets the CPU, it keeps it. (e.g., FCFS, SJF).
- Given the following processes, draw the Gantt chart and calculate the average waiting time for Priority Scheduling (Preemptive).
- P1: Arrival=0, Burst=10, Priority=3 (Lower number = Higher priority) - P2: Arrival=2, Burst=1, Priority=1 - P3: Arrival=3, Burst=2, Priority=2
Answer: - Time 0-2: P1 runs (Only process available). - Time 2: P2 arrives (Priority 1 > 3). P1 preempted. P2 runs. - Time 2-3: P2 finishes. - Time 3: P3 arrives (Priority 2). P1 (Priority 3) is waiting. P3 runs. - Time 3-5: P3 finishes. - Time 5-15: P1 runs to completion. - Gantt Chart: | P1 (0-2) | P2 (2-3) | P3 (3-5) | P1 (5-15) | - Waiting Time: - P1 = (2-0) + (5-3) = 2 + 2 = 4 (Waited for P2 and P3) - P2 = 0 - P3 = 0 (Started immediately at time 3) - Average = (4 + 0 + 0) / 3 = 1.33 ms. - What are the two fundamental models of Inter-Process Communication (IPC)?
Answer:
- Shared Memory: A region of memory is established that is shared between processes. Processes can exchange data by reading/writing to this region. Fast but requires synchronization (e.g., using semaphores) to prevent race conditions.
- Message Passing: Communication occurs via messages exchanged between processes. The OS provides system calls like send(message) and receive(message). Slower due to kernel intervention but easier to implement and used in distributed systems.
- What is a Race Condition?
Answer: A race condition occurs when multiple processes or threads access and manipulate the same shared data concurrently, and the outcome of the execution depends on the specific order in which the operations are executed. If the order is incorrect, the final result becomes inconsistent.
- What is a Semaphore? Explain the difference between a binary semaphore and a counting semaphore.
Answer: A semaphore is a synchronization primitive used to control access to shared resources. It is essentially a protected integer variable.
- Binary Semaphore (Mutex): Takes values 0 and 1. Used for mutual exclusion to ensure only one process enters the critical section at a time.
- Counting Semaphore: Can take values from 0 to N. Used to manage multiple instances of a resource (e.g., 5 printers). The value indicates the number of available resources.
- What is Deadlock? What are the 4 necessary conditions for Deadlock?
Answer: Deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process in the set. None of them can proceed. The four necessary conditions (Coffman conditions) are:
- Mutual Exclusion: Only one process can use the resource at a time.
- Hold and Wait: A process holds at least one resource and is waiting for additional resources held by other processes.
- No Preemption: Resources cannot be forcibly taken away; they are released voluntarily.
- Circular Wait: A set of processes exists where P1 is waiting for a resource held by P2, P2 for P3, ..., Pn is waiting for a resource held by P1.
- What is a Thread? How is it different from a Process?
Answer: A thread is the smallest unit of execution. A process can have multiple threads (multithreading).
- Process: Heavyweight. Has its own memory space, address space, and resources. Context switching is expensive.
- Thread: Lightweight. Shares the memory address space and resources of its parent process. Context switching is cheaper.
- Key difference: Threads share memory, making communication between threads easy but risky (synchronization needed). Processes have isolated memory, making communication harder but providing better security.
- What is the difference between User-level threads and Kernel-level threads?
Answer:
- User-level threads: Managed by a thread library in user space (e.g., POSIX Pthreads). The OS kernel is unaware of them. Fast to create and switch but blocking one thread blocks the whole process, and they cannot utilize multiprocessor systems effectively.
- Kernel-level threads: Managed directly by the operating system kernel. Slower to create and switch (because of system calls). However, if one thread blocks, the kernel can schedule another thread, and they can run on different CPUs in parallel.
- Explain the 5-state process model with a diagram (in words).
Answer: The 5-state model adds New and Terminated to the basic Running/Ready/Waiting model:
- New: Process is being created (loading into memory).
- Ready: Process is in memory and waiting for CPU.
- Running: Process is executing on the CPU.
- Blocked/Waiting: Process is waiting for an event (e.g., I/O).
- Exit/Terminated: Process has finished and is releasing resources.
- Transitions: New -> Ready (Admitted). Ready -> Running (Dispatch). Running -> Ready (Interrupt or Time-out). Running -> Blocked (I/O request). Blocked -> Ready (I/O completion). Running -> Exit (Release).
- How does the OS use the Ready Queue and Wait Queue?
Answer:
- Ready Queue: A list of all processes residing in main memory that are ready and waiting to execute on the CPU. The scheduler selects a process from this queue to be dispatched to the CPU.
- Wait Queue (Device Queue): A list of processes waiting for a specific I/O device or event (e.g., a printer or a disk read). When an I/O request is made, the process is moved from the Ready Queue to the appropriate Wait Queue. When the I/O completes, the process is moved back to the Ready Queue.
- A system uses a single CPU. Process A has a CPU burst of 100ms, Process B has a burst of 1ms, and Process C has a burst of 1ms. If they all arrive at time 0, which scheduling algorithm yields the lowest average waiting time, and why?
Answer:
- SJF yields the lowest average waiting time. - FCFS: A (100), B (1), C (1) -> Waiting: A=0, B=100, C=101. Avg = 67ms. - SJF: B (1), C (1), A (100) -> Waiting: B=0, C=1, A=2. Avg = 1ms.Reason: SJF moves the short jobs to the front. This minimizes the time that short jobs spend waiting, drastically reducing the overall average, even though the long job (A) waits slightly longer than in FCFS (where it waits 0). This illustrates that SJF is provably optimal for minimizing average waiting time.